import java.util.Scanner;

public class MaxSubarraySum {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        //输入数组长度
        System.out.print("请输入数组长度：");
        int n = scanner.nextInt();
        int[] nums = new int[n];

        //输入数组元素
        System.out.println("请输入" + n + "个整数（用空格分隔）：");
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        //计算最大子数组和及对应子数组
        Result result = findMaxSubarray(nums);

        //输出结果
        System.out.println("最大子数组和为：" + result.maxSum);
        System.out.print("对应的子数组为：[");
        for (int i = result.start; i <= result.end; i++) {
            System.out.print(nums[i]);
            if (i != result.end) {
                System.out.print(", ");
            }
        }
        System.out.println("]");

        scanner.close();
    }

    // 用于存储最大子数组的结果（和、起始索引、结束索引）
    static class Result {
        int maxSum;
        int start;
        int end;

        Result(int maxSum, int start, int end) {
            this.maxSum = maxSum;
            this.start = start;
            this.end = end;
        }
    }

    // 查找最大子数组（返回和及起始、结束索引）
    public static Result findMaxSubarray(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("数组不能为空");
        }

        int maxCurrent = nums[0];
        int maxGlobal = nums[0];
        int start = 0;      // 当前子数组起始索引
        int tempStart = 0;  // 临时起始索引（用于更新起始点）
        int end = 0;        // 最大子数组结束索引

        for (int i = 1; i < nums.length; i++) {
            // 决定是否从当前元素重新开始子数组
            if (nums[i] > maxCurrent + nums[i]) {
                maxCurrent = nums[i];
                tempStart = i;  // 更新临时起始索引
            } else {
                maxCurrent += nums[i];
            }

            // 更新全局最大值及对应的索引
            if (maxCurrent > maxGlobal) {
                maxGlobal = maxCurrent;
                start = tempStart;  // 确定起始索引
                end = i;            // 确定结束索引
            }
        }

        return new Result(maxGlobal, start, end);
    }
}
    